/*
Date:20210414 23:17pm
key华为笔试题
*/
class Solution {
public:

void jump1(int* A, int* B,int &i, int& n)
{
    //遍历i及的右边A[i]个
    int new_i=i;
    int j;
    int max_len = 0;
    for (j = i; j <= i + A[i]&&j<n; j++)
    {

        if (B[j] >= max_len)
        {
            new_i = j;
            max_len = B[j];

        }
    }
    i = new_i;
}

    int jump(vector<int>& nums) {
	int i, j, n;
	n=nums.size();
	if (n == 0) { cout << 0; return 0; }
	int* A = new int[n];
	for (i = 0; i < n; i++)
	{
		A[i]=nums[i];
	}
	//每个点能到的最远
	int* B = new int[n];
	for (i = 0; i < n; i++)
	{
		B[i] = i + A[i];
	}
	i = 0;
	int count = 0;
	while (1)
	{
		//每次把下标起点放入
		jump1(A, B, i, n);
		//cout << i << " ";
		count++;
		//因为i是下标所以要+1
		if (i + 1 >= n)
		{
			return count;
		}

	}
    return count;
    }
};